package io.adrainty.algorithm.leetcode.normal;

/**
 * @author adrainty
 * @version v1.0.0
 * @since 2024/12/26 下午4:15
 */
public class Solution91 {

    public int numDecodings(String s) {
        s = s.replace("10", "A");
        s = s.replace("20", "A");
        if (s.contains("0")) return 0;
        return 1 + helper(s);
    }

    private int helper(String s) {
        if (s.isEmpty()) return 0;
        if (s.length() == 1) return 1;
        if (s.charAt(0) == '1' && s.charAt(1) != 'A') {
            return 1 + Math.max(helper(s.substring(1)), helper(s.substring(2)));
        } else if (s.charAt(0) == '2') {
            if (s.charAt(1) >= '0' && s.charAt(1) <= '6') {
                return 1 + Math.max(helper(s.substring(1)), helper(s.substring(2)));
            } else {
                return helper(s.substring(1));
            }
        } else {
            return helper(s.substring(1));
        }
    }

    public static void main(String[] args) {
        System.out.println(new Solution91().numDecodings("12"));
    }

}
